# 1+2+3+4+....
# 1*2*3*4*5....
# 1 1 2 3 5 8 13 21...

# 通过重复将问题分解为同类的子问题而解决问题的方法
# 把问题分解成为规模更小的、具有与原问题有着相同解法的问题。
# 比如二分查找算法，就是不断地把问题的规模变小（变成原问题的一半），而新问题与原问题有着相同的解法。
# [1,2,3,4,5,6,7,8,9,10]
#
# 能用递归来解决的问题必须满足两个条件：
# 存在一种简单情境，可以使递归在简单情境下退出。
    # 出口条件，即递归“什么时候结束”，这个通常在递归函数的开始就写好;
# 可以通过递归调用来缩小问题规模，且新问题与原问题有着相同的形式。
    # 如何由"情况 n" 变化到"情况 n+1", 也就是非出口情况，也就是一般情况——"正在"递归中的情况；


# 求n! => 1*2*3....*n


def jiecheng(n):
    result = 1
    for i in range(1,n+1):
        print(i)
        result *=i
    return result
print(jiecheng(5))


# 出口：n = 1
# 缩小问题规模:   n!
# n * n-1
# n=1
# n * n-1 * n-2 * n-3


def jiecheng(n):
    # 出口条件
    if n == 1:
        return 1
    else:
        return n * jiecheng(n-1)

print(jiecheng(5))

def feb(n):
    if n==0 or n==1:
        return 1
    else:
        return feb(n-1)+feb(n-2)

for i in range(5):
    print(feb(i),end=',')


